package 数据结构;

import java.util.Scanner;
import java.util.Stack;

/*
数据结构中的栈，在解决很多问题都有用处，比如括号匹配，迷宫求解，表达式求值等等
        java中有封装好的类，可以直接调用：
        Stack:
        1-->public Stack()          创建一个空堆栈
        2-->public boolean empty()  测试堆栈是否为空;
        3-->public E pop()          移除堆栈顶部的对象，并作为此函数的值返回该对象。
        4-->public E push(E item)   把项压入堆栈顶部
        5-->public E peek()         查看堆栈顶部的对象，但不从堆栈中移除它。
        6-->public boolean empty()  测试堆栈是否为空

结合一道题目：

括号配对问题:
1、描述
现在，有一行括号序列，请你检查这行括号是否配对。
2、输入
第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S
(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符
3、输出
每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No
4、样例输入
3
[(])
(])
([[]()])
5、样例输出
No
No
Yes
*/
public class StackTest {
    /**/
    public static void main(String[] args) {
        //1、输入数据
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入要测试几组测试数据：");
        int totalNum = scanner.nextInt();
        System.out.println("请输入要测试括号是否匹配的字符串：");
        for (int i = 0; i < totalNum; i++) {
            System.out.print("第" + i + "组数据：");
            String s = scanner.next();  //注意：要输入[]()这样的字符，所以必须使用next()而不是nextLine()
            if (isMatch(s)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    //按照题意
    private static boolean isMatch(String s) {
        //1.1 创建数据结构：堆(存放字符元素)
        Stack<Character> stack = new Stack<Character>();
        //遍历字符串字符，将左括号存入栈中，遇到右括号时，则出栈匹配
        for (int i = 0; i < s.length(); i++) {
            //2.1、存左括号
            if (s.charAt(i) == '(' || s.charAt(i) == '[') { //字符ASCII值判断
                stack.push(s.charAt(i));
            }
            //2.2、遇到右括号，从栈中取出(需要栈非空)括号匹配
            if (s.charAt(i) == ')') {
                if (!stack.isEmpty() && stack.pop() == '(') { //栈非空且弹出为匹配的字符
                    continue; //括号匹配上了，继续查找后面的是否匹配
                } else {
                    return false; //括号没匹配上，返回false
                }
            }
            if (s.charAt(i) == ']') {
                if (!stack.isEmpty() && stack.pop() == '[') {
                    continue; //括号匹配上了，继续查找后面的是否匹配
                } else {
                    return false; //括号没匹配上，返回false
                }
            }
        }
        //3、查看栈中元素是否全部弹出
        if (stack.isEmpty()) {
            return true;  //栈中元素全部弹出
        } else {
            return false;  //栈中还有没弹出的，也出错
        }
    }

}
